\documentclass[]{beamer}
% vim: set expandtab spell:

\setbeamercovered{transparent}
% This file is a solution template for:

% \setbeamertemplate{navigation symbols}{} 

% - Talk at a conference/colloquium.
% - Talk length is about 20min.
% - Style is ornate.

%\usetheme{AnnArbor}
%\usetheme{Antibes}
%\usetheme{Bergen} % NAO
%\usetheme{Berkeley} % NAO
%\usetheme{Berlin}
%\usetheme{Boadilla}
%\usetheme{boxes} % NAO
%\usetheme{CambridgeUS}
%\usetheme{Copenhagen}
%\usetheme{Darmstadt} % QUASE
%\usetheme{default} % NAO
%\usetheme{Dresden}
%\usetheme{Frankfurt}
%\usetheme{Goettingen} % not bad, but not for this
%\usetheme{Hannover}
%\usetheme{Ilmenau} % BOM
%\usetheme{JuanLesPins}
%\usetheme{Luebeck}
\usetheme{Madrid}
%\usetheme{Malmoe}
%\usetheme{Marburg}
%\usetheme{Montpellier}
%\usetheme{PaloAlto} % nao com este logo
%\usetheme{Pittsburgh}
%\usetheme{Rochester} % QUASE
%\usetheme{Singapore} % NICE
%\usetheme{Szeged}
%\usetheme{Warsaw}

% Copyright 2004 by Till Tantau <tantau@users.sourceforge.net>.
%
% In principle, this file can be redistributed and/or modified under
% the terms of the GNU Public License, version 2.
%
% However, this file is supposed to be a template to be modified
% for your own needs. For this reason, if you use this file as a
% template and not specifically distribute it as part of a another
% package/program, I grant the extra permission to freely copy and
% modify this file as you see fit and even to delete this copyright
% notice. 


%\mode<presentation>
%{
%  \usetheme{Warsaw}
%  % or ...
%
%  \setbeamercovered{transparent}
%  % or whatever (possibly just delete it)
%}


%\usepackage[portuges]{babel}
\usepackage[utf8]{inputenc}

\usepackage{epstopdf}
\usepackage[]{graphicx}

\usepackage{times}
\usepackage[T1]{fontenc}
\usepackage{ae}
\usepackage{proof,amsmath, amsthm, amssymb, txfonts, calc, mdwlist, stmaryrd,verbatim, cmll, hyperref, fancybox}
\newcommand{\bnu}{\boldsymbol{\nu}}

\newcommand{\lts}[1]{\stackrel{\small{#1}}{\longrightarrow}}
%\usepackage{mathpartir}

\title[] % (optional, use only with long paper titles)
{15-740 Project: Branch Prediction \\ (Milestone 2)}

%\subtitle
%{Include Only If Paper Has a Subtitle}

\author[Branch Prediction]{Bernardo Toninho, Ligia Nistor, Filipe Milit\~{a}o}
\institute[15-740 Class Project]
%\institute[CMU \& FCT-UNL] % (optional, but mostly needed)
%{
%Carnegie Mellon University \& Universidade Nova de Lisboa
%}
% - Use the \inst command only if there are several affiliations.
% - Keep it simple, no one is interested in your street address.

% If you have a file called "university-logo-filename.xxx", where xxx
% is a graphic format that can be processed by latex or pdflatex,
% resp., then you can add a logo as follows:

%\pgfdeclareimage[width=2cm]{university-logo}{fct}
%\logo{\pgfuseimage{university-logo}}


% Delete this, if you do not want the table of contents to pop up at
% the beginning of each subsection:
%\AtBeginSubsection[]
%{
%  \begin{frame}<beamer>
%    \frametitle{Percurso}
%    \tableofcontents[currentsection,currentsubsection]
%  \end{frame}
%}


% If you wish to uncover everything in a step-wise fashion, uncomment
% the following command: 

%\beamerdefaultoverlayspecification{<+->}


\begin{document}

\maketitle

%\begin{frame}
%  \frametitle{Outline}
%  \tableofcontents
%  % You might wish to add the option [pausesections]
%\end{frame}

%\section{Report Context}

\begin{frame}
\frametitle{Project Context}
\begin{block}{Branch Prediction}
	\begin{itemize}
	\item A fundamental component of
          micro-architectures: tries to \textit{predict} future paths to keep the pipeline full, avoid stalls.
        \item Misprediction penalty proportional to pipeline depth.
        \item Key constraints: needs to be \textbf{fast}, \textbf{simple} and
          \textbf{highly accurate}!
        \item Varied design space: local/global history based
          predictors, machine learning-based predictors, etc.    
	\end{itemize}
\end{block}
\pause
\begin{block}{Hybrid Branch Predictors}
	\begin{itemize}
	\item Each predictor has its own set of strengths/limitations.
	\item Idea: combine multiple predictors (try to get the
          ``best of both worlds'').
        \item Problem 1: What predictors should be combined? 
        \item Problem 2: How to dynamically choose between the component predictors to make the most accurate prediction?
	\end{itemize}
\end{block}
\end{frame}

\begin{frame}
\frametitle{Our Approach: Hybrid Predictor}

\begin{block}{Typical Hybrid Predictor}
\begin{itemize}
\item Combines two predictors: usually a global predictor and a ``specialized'' predictor
  (local predictor, loop predictor).
\item Decides using a PC-indexed table of 2-bit saturating counters.
%$${\scriptsize \mbox{PC}\rightarrow \mbox{ComponentDecisionTable}}$$
\end{itemize}
\pause
\end{block}
\begin{block}{A \textit{smarter} meta-predictor}
\begin{itemize}
\item Exploit additional information available to the meta-predictor:
\item[-] Index using a hash of the \textit{global history} and the \textit{PC}.
$${\scriptsize\overbrace{0101010..10101}^{\mbox{branch history}}  ~\oplus~ \mbox{PC}\rightarrow \mbox{ComponentDecisionTable}}$$
\item[-] Potentially allows the hybrid to choose more accurately between the two components, by exploiting inter-branch correlation.
\end{itemize}
\end{block}

\end{frame}

\begin{frame}
\frametitle{Evaluation Methodology}
\begin{block}{Simulation Infrastructure}
\begin{itemize}
\item Championship Branch Prediction (CBP) simulator.
\item Simple out-of-order 14 stage pipeline, 4-wide pipeline, 12-wide
  execution scheduler.
\item Outputs a very simple score based on misprediction penalty.
\item We extended the simulator with some customized statistics:
\begin{itemize}
\item Prediction progress ( mispredictions per branch execution );
\item Branch classification metrics ( taken percentage, transition frequency );
\item Branch trace ( how each prediction compares to the real behavior);
\end{itemize}
\end{itemize}
\end{block}
\pause
\begin{block}{Implemented Predictors}
\begin{itemize}
\item Baseline predictors: \textit{gshare}, \textit{perceptron}, \textit{o-gehl}, \textit{piecewise}, \textit{last}, \textit{always taken}, \textit{never taken}, \textit{random}, \textit{local};
\item Hybrids (with two variants for each meta-prediction scheme): gshare+local, perceptron+local, gshare+perceptron.
\end{itemize}
\end{block}
\end{frame}


\begin{frame}
\frametitle{Preliminary Results}
\begin{center}
\begin{tabular}{cc}
Misprediction Rates\\
\includegraphics[scale=0.28]{aggregate}
\end{tabular}
\end{center}
\end{frame}



\begin{frame}
\frametitle{Preliminary Results}
\begin{center}
\begin{tabular}{cc}
Classifying Branches in Server Benchmark\\
\includegraphics[scale=0.25]{classes_server02}
\end{tabular}
\end{center}
Most branches are never or rarely taken (history
doesn't help much here).
\end{frame}

\begin{frame}
\frametitle{Preliminary Results}
\begin{center}
\begin{tabular}{cc}
Classifying Wrong Predictions in Server Benchmark\\
\includegraphics[scale=0.25]{wrong_server02}
\end{tabular}
\end{center}
44\% of the wrong predictions couldn't have been improved anyway\dots
\end{frame}

\begin{frame}
\frametitle{Preliminary Results}
\begin{block}{Wrong Decisions vs Optimal}
\begin{center}
{\tiny
% MM01 SEVER02
\begin{tabular}{| c | c | c || c | c | c |}
%% mm01
\hline
Test & Hybrid & Wrong Decisions & Miss Rate & Optimal & Difference \\
\hline
Multimedia & gshare + local(h1) & 34.0 \% & 7.4 \% & 2.9 \% & 4.5 \%\\
Multimedia & gshare + local(h2) & 27.3 \% & 6.5 \% & 2.9 \% & 3.6 \%\\
Multimedia & perceptron + local(h1) & 39.2 \% & 12.0 \% & 6.4 \% & 5.6 \% \\
Multimedia & perceptron + local(h2) & 34.5 \% & 10.9 \% & 6.4 \% & 4.5 \% \\
\hline
%%server02
Server & gshare + local(h1) & 24.8 \% & 2.8 \% & 1.4 \% & 1.4 \% \\
Server & gshare + local(h2) & 29.5 \% & 3.1 \% & 1.4 \% & 1.7 \%\\
Server & perceptron + local(h1) & 12.6 \% & 4.6 \% & 2.6 \% & 2.0 \%\\
Server & perceptron + local(h2) & 10.3 \% & 4.1 \% & 2.6 \% & 1.5 \%\\
\hline
\end{tabular}}\end{center}
\end{block}
\pause
\begin{block}{Summary}
\begin{itemize}
\item We performed similar analyses using different benchmark classes.
\item Overall, our hybrid scheme was mostly better than the
  existing one.
\item When it is worse, only slightly. Correlated non-typical branch
  behavior (as shown previously).
\end{itemize}
\end{block}

\end{frame}

\begin{frame}
\frametitle{Next milestone's goals}

\begin{itemize}
\item Compare with other predictors - namely this year's CBP winners
  (preliminary results show we are not quite there yet);
\item Further performance improvements - try to exploit the branch
  classification results to improve the meta-predictors;
\item Implementation fixes - some predictors do not behave as well as expected (\textit{o-gehl}, \textit{piecewise}, \textit{perceptron}) and need to be fixed;
\item Consistent decision on ``cheating'' - some implementations use a pseudo-cheat such as updating the branch history with the correct branch outcome at \textit{fetch} stage although such result is only known at \textit{retire} - but removing it yields poor performance inconsistent with the results in literature.
\end{itemize}

\end{frame}


\begin{frame}
\begin{center}
\begin{tabular}{cc}
Classifying Branches in Multimedia Benchmark\\
\includegraphics[scale=0.25]{classes_mm01}
\end{tabular}
\end{center}
\end{frame}

\begin{frame}
\begin{center}
\begin{tabular}{cc}
Branch Re-execution Distribution in Server\\
\includegraphics[scale=0.25]{distribution_server02}
\end{tabular}
\end{center}
\end{frame}



\end{document}






